// 前缀树节点定义
class Trie
{
public:
    Trie *children[26];
    Trie()
    {
        for(int i = 0; i < 26; i++)
            children[i] = nullptr;
    }
};
class Solution 
{
public:
    int minValidStrings(vector<string>& words, string target)
    {
        // 构建前缀树
        Trie *root = new Trie();
        for(const string &word : words)
        {
            Trie *node = root;
            for(const char &ch : word)
            {
                int idx = ch - 'a';
                if(node->children[idx] == nullptr)
                    node->children[idx] = new Trie();
                node = node->children[idx];
            }
            // 在这个问题中，任何前缀都是有效的，不需要标记结束
        }

        // dp[i] 表示构造 target 的前 i 个字符所需的最少有效字符串数量
        // 初始化 dp[0] = 0，表示空字符串需要0个有效字符串
        int n = target.size();
        const int INF = INT_MAX;
        vector<int> dp(n + 1, INF);
        dp[0] = 0;

        for(int i = 0; i < n; i++)
        {
            // 如果 dp[i] 是无穷大，说明当前位置无法通过已知的有效字符串达到，跳过
            if(dp[i] == INF)
                continue;

            Trie *node = root;
            for(int j = i; j < n; j++)
            {
                int idx = target[j] - 'a';
                if(node->children[idx] == nullptr)
                    break;
                node = node->children[idx];
                dp[j + 1] = min(dp[j + 1], dp[i] + 1);
            }
        }
        return dp[n] == INF ? -1 : dp[n];
    }
};